微信公众号:BoomDev
如有问题或建议请留言
最近更新:2018-10-03
读《数据结构与算法》笔记-链表如何实现 LRU 缓存淘汰算法
链表(Linked List)经典的应用场景就是 LRU 缓存淘汰算法,常见的策略有三种:先进先出 FIFO(First In,First Out)、最少使用策略 LFU (Least Frequently Used)、最近最少使用策略 LRU (Least Recently Used)
数组和链表区别
如果我们申请一个 100MB 大小的数组,当内存中没有连续的、足够大的存储空间时,即便内存剩余总可用空间大于 100MB 仍然会申请失败。
而链表不需要一块连续的内存空间,通过“指针”将一组零散的内存块串联起来,在这种情况下根本不会有问题。
- 单链表
第一个节点叫做头节点,最后一个节点叫做尾节点。头节点用来记录链表的基地址,有了它就可以遍历得到整条链表,尾节点指向一个空地址 NULL ,表示这是链表的最后一个节点。
链表也支持数据的查找、插入和删除操作。
链表不需要连续的内存空间存储数据,所以在链表中插入和删除操作非常快。插入和删除的时间复杂度是 O(1),随机访问的时间复杂度是 O(n)。
- 循环链表
循环链表是一种特殊的单链表,尾节点指向链表的头节点。循环链表的优点是从尾节点到头节点比较方便。当要处理的数据具有环型结构特点时,就特别适合采用循环链表,比如:约瑟夫问题
- 双向链表
它支持两个方向,一个后继指针 next 指向后面的节点,一个前驱指针 prev 指向前面的节点。双向链表需要额外的两个空间来存储后继节点和前驱节点,所以比单链表占用更多的存储空间,但可以支持双向遍历。
链表中删除数据的两种情况:
- 删除节点中
值等于某个给定值
的节点 - 删除给定指针指向的节点
对于第一种情况,都需要从头节点开始一个一个遍历直到找到给定值的节点,再通过指针操作将其删除。单纯的删除操作时间复杂度是 O(1),但是为了遍历查找,对应的时间复杂度是 O(n) 所以删除值等于给定值的节点对应的链表操作的时间复杂度是O(n)
第二种情况,单链表不支持直接获取前驱节点,所以还是要从头开始遍历链表,时间复杂度是O(n)。对于双向链表,这种情况就比较有优势了,双向链表保存了前驱节点的指针,不需要像单链表那样遍历,时间复杂度是O(1)。
链表 VS 数组性能
链表实现缓存淘汰算法
思路:维护一个有序单链表,当有新的数据访问时,就从链表头开始遍历链表。
1、如果数据缓存在链表中,遍历到数据对应的节点删除,然后再插入到链表的头部
2、如果数据没有缓存在链表中
- 缓存没满,直接插入到链表的头部
- 缓存满了,删除尾节点,将新的数据节点插入链表的头部
我是一名有备而来的 Android 工程师
微信公众号:BoomDev
欢迎关注我、一起学习、一起进步!